#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <functional>

using namespace std;

// 988. 从叶结点开始的最小字符串
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution1
{
public:
    string smallestFromLeaf(TreeNode *root)
    {
        string ret;
        function<void(TreeNode *, string)> dfs = [&](TreeNode *node, string path)
        {
            if (!node)
                return;
            path = char(node->val + 'a') + path;
            if (!node->left && !node->right)
            {
                if (ret.empty() || path < ret)
                {
                    ret = path;
                }
            }
            dfs(node->left, path);
            dfs(node->right, path);
        };

        dfs(root, "");
        return ret;
    }
};

// 2415. 反转二叉树的奇数层
class Solution2
{
public:
    TreeNode *reverseOddLevels(TreeNode *root)
    {
        int depth = 0;
        vector<TreeNode *> v;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty())
        {
            int sz = q.size();
            for (int i = 0; i < sz; ++i)
            {
                TreeNode *t = q.front();
                q.pop();
                if (depth % 2 == 1)
                    v.push_back(t);
                if (t->left)
                {
                    q.push(t->left);
                    q.push(t->right);
                }
            }

            if (depth % 2 == 1)
            {
                int left = 0, right = v.size() - 1;
                while (left < right)
                {
                    int tmp = v[left]->val;
                    v[left]->val = v[right]->val;
                    v[right]->val = tmp;
                    ++left;
                    --right;
                }
                v.clear();
            }

            ++depth;
        }

        return root;
    }
};

// 1170. 比较字符串最小字母出现频次
class Solution3
{
public:
    vector<int> numSmallerByFrequency(vector<string> &queries, vector<string> &words)
    {
        auto f = [](string s)
        {
            int cnt[26] = {0};
            for (char c : s)
            {
                cnt[c - 'a']++;
            }
            for (int x : cnt)
            {
                if (x)
                {
                    return x;
                }
            }
            return 0;
        };
        int n = words.size();
        int nums[n];
        for (int i = 0; i < n; i++)
        {
            nums[i] = f(words[i]);
        }
        sort(nums, nums + n);
        vector<int> ans;
        for (auto &q : queries)
        {
            int x = f(q);
            ans.push_back(n - (upper_bound(nums, nums + n, x) - nums));
        }
        return ans;
    }
};

// 1785. 构成特定和需要添加的最少元素
class Solution4
{
public:
    int minElements(vector<int>& nums, int limit, int goal) 
    {
        long long sum = 0;
        for(int x : nums) sum += x;
        long long diff = abs(sum - (long long)goal);
        if(diff % limit == 0)
            return diff / limit;
        else
            return diff / limit + 1;
    }
};

// 994.腐烂的橘子
class Solution5
{
public:
    int orangesRotting(vector<vector<int>>& grid) 
    {
        queue<pair<int, int>> q;
        int m = grid.size(), n = grid[0].size();
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j] == 2) q.emplace(i, j);
            }
        }

        int dx[4] = {0, 0, -1, 1};
        int dy[4] = {1, -1, 0, 0};
        int step = 0;
        while(!q.empty())
        {
            int sz = q.size();
            bool flag = false;
            while(sz--)
            {
                auto [i, j] = q.front();
                q.pop();
                for(int k = 0; k < 4; ++k)
                {
                    int x = i + dx[k], y = j + dy[k];
                    if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1)
                    {
                        flag = true;
                        grid[x][y] = 2;
                        q.emplace(x, y);
                    }
                }
            }
            if(flag) ++step;
        }

        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j] == 1) return -1;
            }
        }
        return step;
    }
};